// T-408-STNE
// Operating systems and networks
// Spring 2011
// Programming assignment 2: Page replacement algorithms
//
// Implementation of the FIFO page replacement algorithm. You do not have to modify this code.
// Based on code by Olafur R. Helgason

import java.io.*;
import java.util.*;

public class ClockAlgorithm {
    //
    // ClockAlgorithm
    //
    // Class constructor. Also runs the experiment on the page references given in memString
    // The memory is represented as a linked list, ordered by time of reference so the head is the
    // oldest and the tail the most recent. Note that you may need a different memory representation
    // for your algorithms.
    //
    public ClockAlgorithm(int memSize, int memString[]) {
        // The usual initialization.
        _pageFaults = 0;
        _memory = new int[memSize];
        _reference = new int[memSize];
        _memSize = memSize;

        _index = 0;             // index pointer
        _refIndex = 0;               // reference index pointer


        // Run our experiment
        for (int i = 0; i < memString.length; i++)
            memAccess(memString[i]);
    }


    //
    // memAccess
    //
    // Access a virtual memory page. We count a page fault if the virtual page is not in
    // memory.
    //
    private void memAccess(int page) {

        if (!containsPage(page)) {

            pageFault(page);
            _index = (_index + 1) % _memSize;     //move the pointer

        } else {

            _reference[_refIndex] = 1;                //when page is in memory we reference it so it stays there
        }
    }

    //Function that looks upp page in memory if it finds it then
    //we set the reference index pointer for modification
    private boolean containsPage(int page) {
        for (int i = 0; i < _memSize; i++) {
            int j = _memory[i];
            if (j == page) {
                _refIndex = i;
                return true;
            }
        }
        return false;
    }

    //
    // pageFault
    //
    // Page fault handling. This is the section of code that you should change in implementing your
    // other page replacement algorithms
    //
    private void pageFault(int page) {

        _pageFaults++; // Increment the page fault counter.

        //while pointer is pointing at reference page it traverse until it points at non-reference bit
        while (_reference[_index] == 1) {
            _reference[_index] = 0;
            _index = (_index + 1) % _memSize;
        }

        _memory[_index] = page;     //we replace the page
        _reference[_index] = 1;     //and set the page as referenced
    }

    //
    // pageFaults
    //
    // Give the total page faults generated in the experiment
    //
    public int pageFaults() {
        return _pageFaults;
    }

    private int[] _memory;        // The simulated memory
    private int _memSize;            // Memory size in page frames
    private int _pageFaults;        // Page fault count
    private int[] _reference;
    private int _index;
    private int _refIndex;
}